package com.formula.datastructure.exam.graph.sp;

import com.formula.datastructure.exercise.graph.undirect.MatrixGraph;

public class Dijkstra {

    private static final int INF = 99999;

    public void getSP(MatrixGraph graph, int start) {
        int N = graph.size;

        int[] distance = new int[N];
        int[] prev = new int[N];
        int[] visited = new int[N];
        for (int i = 0; i < N; i++) {
            prev[i] = start;
        }

        visited[start] = 1;

        for (int i = 0; i < N; i++) {
            distance[i] = graph.edges[start][i];
        }

        for (int i = 0; i < N; i++) {
            int min = INF;
            int nextVer = start;
            for (int j = 0; j < N; j++) {
                if (visited[j] == 0 && distance[j] < min) {
                    min = distance[j];
                    nextVer = j;
                }
            }

            visited[nextVer] = 1;

            for (int j = 0; j < N; j++) {
                if (visited[j] == 0 && distance[j] > distance[nextVer] + graph.edges[nextVer][j]) {
                    prev[j] = nextVer;
                    distance[j] = distance[nextVer] + graph.edges[nextVer][j];
                }
            }
        }
    }
}
